package com.cskaoyan.javase.recursion._1basic;

/**
 * @description: 递归的思想以及危险的递归
 * @author: wuguidong@cskaoyan.onaliyun.com
 **/

/**
 * 递归的两要素
 * - 递归体（方法中自身调用自身方法的那句语句）
 * - 递归出口
 * 递归的思想:
 * 1. 把一个复杂的大规模的问题，分解成若干相似的小规模的子问题
 * 2. 当子问题规模足够小的时候，就可以直接得到小规模问题的解
 * 3. 然后把所有的小规模的子问题的解，组合起来
 * 4. 最终得到大规模问题的解
 * 递归的思想,核心在于分解
 *
 * 案例: 求n的阶乘,n!
 * n! = n * (n-1) * (n-2) * ... * 1;
 * 使用递归求它的结果:
 * n! = n * (n-1)!;
 * (n-1)! = (n-1) * (n-2)!;
 * ...
 * 3! = 3 * 2!;
 * 2! = 2 * 1!;
 * 1! = 1;
 * 综上就可以得出递归的递归体和递归的出口:
 * 假设n的阶乘的结果是f(n)
 * 递归体: f(n) = n * f(n-1);
 * 递归的出口: f(1) = 1;
 *
 * 递归的优缺点
 *      优点:
 *          1.代码简洁优雅,递归写出来的代码都十分简洁
 *          2.递归的思想很符合人类的思考习惯,分解问题解决问题是我们经常做的事情
 *      缺点:
 *          1.危险,容易栈溢出
 *          2.递归的时间复杂度和空间复杂度都不优越,既浪费空间,又耗费时间
 *
 * 递归的缺点是很大的，如非必要，不要使用递归，尤其是开发中！
 *
 */
public class Demo {
    public static void main(String[] args) {
        System.out.println(factorial(6));
    }

    //求n的阶乘
    public static long factorial(int n) {
        //建议写递归先写递归出口
        if (n == 1) return 1;
        return n * factorial(n - 1);
    }
}